#include "Algorithms.h"

//int n, m;
int opt;
int ansMax;
int recordAns;
int assingsCount;

bool fullBust;
bool solutionExist;

QVector<int> freeTime;
QVector<QVector<bool> > used;
QVector<QVector<int> > order;
QVector<QVector<int> > answer;
QVector<QVector<int> > inputVector;
QVector<QVector<int> > preliminaryAnswer;

//*******************************************************//
//********************** Full Bust **********************//

int findNearestTime(int machine, int detail, int time)
{
    //need to assign detail for machine. Function return nearest time.
    //int ans = 0;
    for (int i=0; i<m; i++){
        if (i == machine) continue;
        for (int j=0; j<n; j++)
            if (j == detail && preliminaryAnswer[i][j] != -1){
                bool downOverlap = preliminaryAnswer[i][j] < time + inputVector[machine][detail] &&
                                    preliminaryAnswer[i][j] > time;
                bool upOverlap = preliminaryAnswer[i][j] + inputVector[i][j] < time + inputVector[machine][detail] &&
                                 preliminaryAnswer[i][j] + inputVector[i][j] > time;
                bool upEqualUp = preliminaryAnswer[i][j] + inputVector[i][j] == time + inputVector[machine][detail];
                bool downEqualDown = preliminaryAnswer[i][j] == time;
                bool upGreaterUp = preliminaryAnswer[i][j] + inputVector[i][j] > time + inputVector[machine][detail];
                bool downLowerDown = preliminaryAnswer[i][j] < time;

                if ( downOverlap || upOverlap || upEqualUp || downEqualDown || (upGreaterUp && downLowerDown)){
                    //means conflict
                    //ans += preliminaryAnswer[i][j] + inputVector[i][j];
                    time = preliminaryAnswer[i][j] + inputVector[i][j];
                    i = -1;
                }
            }
    }

    //if (ans == -1) ans = freeTime[machine];
    return time;
}

void assignWork( int machine )
{
    if ( assingsCount == n*m ){
        //all works were assigned
        int mx;
        switch (opt){
        case 0:
            //last end
            mx = -1;
            for (int i=0; i<m; i++)
                if (freeTime[i] > mx) mx = freeTime[i];

            if (mx < ansMax || ansMax == -1) {
                ansMax = mx;
                answer = preliminaryAnswer;
                return;
            }
            break;

        case 1:
            //summ end
            mx = 0;
            for (int i=0; i<m; i++)
                mx += freeTime[i];

            if (mx < ansMax || ansMax == -1) {
                ansMax = mx;
                answer = preliminaryAnswer;
                return;
            }
        }

    }
    //perebor po rabotam
    int nearestTime;
    for (int i=0; i<n; i++)
        if (!used[machine][i])
        {
            nearestTime = findNearestTime( machine, i, freeTime[machine] );
            if (!fullBust && nearestTime + inputVector[machine][i] > recordAns){
                continue;
            }
            preliminaryAnswer[machine][i] = nearestTime;
            int prevFree = freeTime[machine];
            freeTime[machine] = preliminaryAnswer[machine][i] + inputVector[machine][i];
            //if (!fullBust && freeTime[machine] > recordAns)
            used[machine][i] = true;
            assingsCount++;

            assignWork( (machine+1)%m );

            preliminaryAnswer[machine][i] = -1;
            freeTime[machine] = prevFree;
            used[machine][i] = false;
            assingsCount--;
        }
}

void initTask(const QVector<QVector<int> > &input, QVector<QVector<int> > &output, int optimization, bool fullBustFlag)
{
    ansMax = -1;
    assingsCount = 0;
    opt = optimization;
    fullBust = fullBustFlag;
    order.clear();
    m = input.size();
    n = input[0].size();

    order.resize( m );
    answer.resize( m );
    preliminaryAnswer.resize( m );
    used.resize( m );
    freeTime.resize( m );
    for (int i=0; i<order.size(); i++){
        order[i].resize( n );
        answer[i].resize( n );
        preliminaryAnswer[i].resize( n );
        used[i].resize(n);
        for (int j=0; j<n; j++){
            used[i][j] = false;
            preliminaryAnswer[i][j] = -1;
        }
        freeTime[i] = 0;
    }


    inputVector = input;

    solutionExist = false;
}

void FullBust(const QVector<QVector<int> > &input, QVector<QVector<int> > &output, int optimization)
{
    initTask(input, output, optimization, true);

    assignWork(0);

    output = answer;
}

//********************** Full Bust **********************//
//*******************************************************//

//*******************************************************//
//**************** Full Bust with amputations ***********//

int calculateRecord()
{
    int mn;
    int nearestTime;
    int detailTime, detailNumber;
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            mn = 1000000;
            for (int k=0; k<n; k++){
                //nearestTime = findNearestTime(j, k, freeTime[j]);
                if (!used[j][k] && mn > inputVector[j][k]){
                    mn = inputVector[j][k];
                    detailNumber = k;
                }
            }

            //now we have detail to put to machine j at i step
            preliminaryAnswer[j][detailNumber] = findNearestTime(j, detailNumber, freeTime[j]);;
            freeTime[j] = preliminaryAnswer[j][detailNumber] + inputVector[j][detailNumber];
            used[j][detailNumber] = true;
        }
    }

    int ret = -1;
    for (int i=0; i<m; i++)
        if (ret < freeTime[i])
            ret = freeTime[i];
    return ret;
}

void FullBustWithAmputations(const QVector<QVector<int> > &input, QVector<QVector<int> > &output, int optimization)
{
    initTask(input, output, optimization, false);
    recordAns = calculateRecord();
    initTask(input, output, optimization, false);

    assignWork(0);

    output = answer;
}

//**************** Full Bust with amputations ***********//
//*******************************************************//
